package leetcode.templates.arrays;

import java.util.LinkedList;
import java.util.Queue;

public class MaxArrays2PointsDist {
	int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

	public int index(int i, int j, int n) {
		return i * n + j;
	}

	// 数组array上，(x,y)与(u,v)在障碍下的最短距离 array[nextx][nexty] == 0 是障碍
	public int dist(int x, int y, int u, int v, int[][] array) {
		if (x == u && y == v) {
			return 0;
		}
		int m = array.length, n = array[0].length;
		boolean[] been = new boolean[m * n];
		been[this.index(x, y, n)] = true;
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x, y, 0 });
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			x = cur[0];
			y = cur[1];
			int dist = cur[2] + 1;
			for (int i = 0; i < 8; i += 2) {
				int nextx = x + d[i], nexty = y + d[i + 1];
				if (nextx == u && nexty == v) {
					return dist;
				}
				int nextIndex = this.index(nextx, nexty, n);
				if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && !been[nextIndex]
						&& array[nextx][nexty] != 0) {
					queue.add(new int[] { nextx, nexty, dist });
					been[nextIndex] = true;
				}
			}
		}
		return -1;
	}

}
